package 力扣_树算法.遍历;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**二叉树的后序遍历
 * @author zx
 * @create 2022-04-09 11:28
 */
public class 二叉树的后序遍历_145 {
    public List<Integer> postorderTraversal2(TreeNode root) {
        //后序遍历：第三次访问根节点时才能输出根节点的值
        // 为了知道啥时候是第三次访问(左树,右树都访问结束,再次回到根节点时,才叫第三次访问)
        // 引入prev引用
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        //上一个完全处理过的节点(左右根都处理完毕的节点)
        TreeNode prev = null;
        while(!stack.isEmpty() || root != null){
            //先一路向左走到最左
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            //此时左树为空,node取栈顶元素,第二次访问
            root = stack.pop();
            //判断右树是否为空或者被我们访问过(第三次访问root)
            if(root.right == null || root.right == prev){
                res.add(root.val);
                //当前节点node就是最后处理的根节点,更新prev引用,变为node
                prev = root;
                //node如果不置空：死循环重复遍历左子树
                root = null;
            }else{
                //此时右树不为空且没有处理过,需要把根节点再压入栈中,继续处理右子树
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }

    /**
     * @return 递归
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        //递归
        List<Integer> res = new ArrayList<>();
        postOrder(root,res);
        return res;
    }
    private void postOrder(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        postOrder(root.left,list);
        postOrder(root.right,list);
        list.add(root.val);
    }
}
